/// @file HashTable.hh
/// @brief Class definition for a simple hash table

// *************************************************************************

// Copyright© 2010 Texas A&M University, 
//                 College Station, Texas
//                 Contact: R Crosby <rwc@cs.tamu.edu>
//
// Copyright© 2003, 2004 by BiRC -- Bioinformatics Research Center
//                 University of Aarhus, Denmark
//                 Contact: Thomas Mailund <mailund@birc.dk>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// *************************************************************************

#ifndef HASHTABLE_HH
#define HASHTABLE_HH

#include <map>
#include <vector>

#include "HashEncoder.hh"

// *****************************************************************************
/// @brief Base class for a hash table
///
/// User should derive from this class as well as a key encoder class

template < class keyT,
           class dataT >
class HashTable
{

    /// @brief Internal hash table node

    struct Node
    {

	keyT *  _key;
	dataT * _data;
	Node  * _next;

	Node(keyT * k, dataT * d) : _key(k),    _data(d),    _next(NULL) {}
	Node()                    : _key(NULL), _data(NULL), _next(NULL) {}

    };

    vector<Node>            _table;		  // The hash table itself...

    HashEncoder<keyT> *     _encoder;		  // Pointer to the key encoder instance

    // Counters for performance information
    unsigned                _hits;		  // Found in hash
    unsigned                _misses;		  // Not found in hash
    unsigned                _nSlots;		  // Slots in table
    unsigned                _slotsUsed;		  // Slots in use
    unsigned                _chains;		  // Slots with hash chains
    unsigned                _longestChain;	  // Longest slot chain
    unsigned                _keyMem;		  // Memory for hash keys
    unsigned                _dataMem;		  // Used memory for hash data
    unsigned                _dataCap;             // Allocated capacity for data
    unsigned                _keys;                // Number of unique keys

    map<string, unsigned *> _statsMap;		  // Hash statistics

protected:

    // Note the value to tablesize is the bit width of the table (2^s)
    // e.g. 14 for 16384 slots
    virtual void    TableSize ( const unsigned s )
	{ _table.resize(1 << s);
	  _encoder->Slots(s);
	  _nSlots = 1 << s; }

    virtual void    Encoder   ( HashEncoder<keyT> * encoder )
	{ _encoder = encoder; }

public:

    virtual dataT *  Find      ( const keyT &  key );

    virtual void     Insert    ( const keyT &  key,
				 const dataT & data );

    virtual unsigned KeyMem    ( const keyT & )  { return 0; }
    virtual unsigned DataMem   ( const dataT & ) { return 0; }
    virtual unsigned DataCap   ( const dataT & ) { return 0; }

    virtual map<string, unsigned *> & Stats()
	{ return _statsMap; }

    HashTable();
    ~HashTable();

};

// *****************************************************************************
/// @brief Constructor setting up the stats map in particular

template < class keyT, class dataT > 
HashTable < keyT, dataT >::HashTable()
    : _hits(0), _misses(0), _slotsUsed(0), _chains(0), _longestChain(0), _keyMem(0), _dataMem(0), _dataCap(0), _keys(0)
{

    _statsMap.insert ( pair<string, unsigned *> ("Hash Hits",     &_hits));
    _statsMap.insert ( pair<string, unsigned *> ("Hash Misses",   &_misses));
    _statsMap.insert ( pair<string, unsigned *> ("Total Slots",   &_nSlots));
    _statsMap.insert ( pair<string, unsigned *> ("Slots Used",    &_slotsUsed));
    _statsMap.insert ( pair<string, unsigned *> ("Chains",        &_chains));
    _statsMap.insert ( pair<string, unsigned *> ("Longest Chain", &_longestChain));
    _statsMap.insert ( pair<string, unsigned *> ("Key Memory",    &_keyMem));
    _statsMap.insert ( pair<string, unsigned *> ("Data Memory",   &_dataMem));
    _statsMap.insert ( pair<string, unsigned *> ("Data Capacity", &_dataCap));
    _statsMap.insert ( pair<string, unsigned *> ("Unique Keys",   &_keys));

}

// *****************************************************************************
/// @brief Destructor clearing the table

template < class keyT, class dataT > 
HashTable < keyT, dataT >::~HashTable()
{

    typename vector<Node>::iterator i = _table.begin();

    for ( ; i < _table.end(); i++) {
	if ( !(*i)._key ) continue;

	Node * n = &(*i);

	while ( n ) {
	    delete n->_key;
	    delete n->_data;
	    Node *nx = n->_next;
	    if ( n != &(*i) ) delete n;
	    n = nx;
	}

    }

}

// *****************************************************************************
/// @brief Hash table lookup
///
/// User shouldn't have to do anything to user this
/// other than call myclass::Find with the key
///
/// @param key Pointer to the key to check
/// @return Pointer to a copy of the data or NULL if not found

template < class keyT, class dataT > 
dataT * 
HashTable < keyT, dataT >::Find ( const keyT & key )
{
    unsigned i = _encoder->Encode(key);

    if ( ! _table[i]._key ) {			  // Simple case - not found
	_misses++;
	return NULL;
    }

    if ( *(_table[i]._key) == key ) {		  // Simple case - found
	_hits++;
	return new dataT(*(_table[i]._data));	  // Return copy of data
    }

    Node *n = _table[i]._next;			  // Look through chain...
    while (n) {
	if ( *(n->_key) == key ) {		  // Found on chain
	    _hits++;
	    return new dataT(*(n->_data));	  // Return copy of data
	}
	n = n->_next;
    }

    _misses++;					  // Not on chain
    return NULL;
}

// *****************************************************************************
/// @brief Insert a new entry into the hash table
///
/// User shouldn't have to do anything to user this
/// other than call myclass::Insert with the key and data pointers
/// Data and key are copied into the table
///
/// @param key Pointer to the key to insert
/// @param data Pointer to the data to insert

template < class keyT, class dataT > 
void 
HashTable < keyT, dataT >::Insert ( const keyT &  key,
				    const dataT & data)
{
    unsigned i = _encoder->Encode(key);

    if (!_table[i]._key) {			  // Empty slot
	_slotsUsed++;
	_table[i]._key  = new keyT(key);
	_table[i]._data = new dataT(data);
    }
    else {					  // Slot in use...chain
	unsigned cLen = 1;
	Node * n = &(_table[i]);
	if ( !n->_next ) _chains++;	          // New chain
	while ( n->_next ) {			  // Find the end of the chain
	    cLen++;
	    n = n->_next;
	}
	n->_next = new Node( new keyT (key), 
			     new dataT(data) );
	if ( cLen > _longestChain ) _longestChain = cLen;
    }

    _keyMem  += KeyMem(key);
    _dataMem += DataMem(data);
    _dataCap += DataCap(data);
    _keys++;

}

#endif // HASHTABLE_HH
